package ee.ut.algorithmics.project;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class SimilarityJoin {

	private Record[] documents;

	public List<Record[]> allPairsSimilarityJoin(Record[] documents, double t) {
		setDocuments(documents);
		List<Record[]> simPairs = new ArrayList<Record[]>();
		Map<String, List<Integer>> invIndeces = createInvInxList();

		int prefix;
		int recordSize;
		for (int i = 0; i < getDocuments().length; i++) {
			simPairs = findMatches(getDocuments()[i], invIndeces, t);
			recordSize = getDocuments()[i].getRecordSize();
			prefix = recordSize - ((int) Math.ceil(recordSize * t)) + 1;
			for (int j = 0; j < prefix; j++) {
				String key = getDocuments()[i].getToken(j);
				List<Integer> indeces = invIndeces.get(key);
				indeces.add(i);
				invIndeces.put(key, indeces);
			}
		}
		return simPairs;
	}

	private List<Record[]> findMatches(Record record,
			Map<String, List<Integer>> invIndeces, double t) {
		List<Record[]> matchingPairs = new ArrayList<Record[]>();
		Map<Integer, Integer> accumScores = new HashMap<Integer, Integer>();
		int minSize = (int) (record.getRecordSize() * (t * t));

		// for all i = 1 -> |r| do
		for (int i = 0; i < record.getRecordSize(); i++) {
			String key = record.getToken(i);
			List<Integer> indeces = invIndeces.get(key);

			// remove all y from Ir[i]
			for (Iterator<Integer> iter = indeces.iterator(); iter.hasNext();) {
				if (getDocuments()[iter.next()].getRecordSize() < minSize) {
					iter.remove();
				}
			}
			invIndeces.put(key, indeces);
			for (Integer recordId : indeces) {
				if (accumScores.containsKey(recordId)) {
					accumScores.put(recordId, accumScores.get(recordId) + 1);
				} else {
					accumScores.put(recordId, 1);
				}
			}
		}
		for (Map.Entry<Integer, Integer> accumScore : accumScores.entrySet()) {
			Record suffix = createRecordSuffix(
					getDocuments()[accumScore.getKey()], t);
			if (((accumScore.getValue() + suffix.getRecordSize()) / Math
					.sqrt(record.getRecordSize()
							* getDocuments()[accumScore.getKey()]
									.getRecordSize())) >= t) {
				double result = (accumScore.getValue() + overlap(record, suffix))
						/ Math.sqrt(record.getRecordSize()
								* getDocuments()[accumScore.getKey()]
										.getRecordSize());
				if (result >= t) {
					matchingPairs.add(new Record[] { record,
							documents[accumScore.getKey()] });
				}
			}
		}

		return matchingPairs;
	}

	private Record createRecordSuffix(Record record, double t) {
		int recordSize = record.getRecordSize();
		int prefix = recordSize - ((int) Math.ceil(recordSize * t)) + 1;
		Record suffixRecord = new Record();
		for (int i = prefix; i < recordSize; i++) {
			suffixRecord.addToken(record.getToken(i));
		}
		return suffixRecord;
	}

	private int overlapUsingHash(Record r, Record y) {
		int overlap = 0;
		Map<String, String> tokenMap = new HashMap<String, String>();

		// Insert all the tokens from r into the hashmap
		for (String token : r.getTokens()) {
			tokenMap.put(token, token);
		}

		// Check if the tokens in y are present in the map
		for (String token : y.getTokens()) {
			if (tokenMap.containsKey(token)) {
				overlap++;
			}
		}

		return overlap;
	}

	private int overlapUsingHashMod(Record r, Record y) {
		int overlap = 0;
		Map<String, Integer[]> tokenMap = new HashMap<String, Integer[]>();

		// Insert all the tokens from r into the hashmap
		for (String token : r.getTokens()) {
			if (tokenMap.containsKey(token)) {
				Integer[] tokens = tokenMap.get(token);
				tokens[0]++;
				tokenMap.put(token, tokens);
			} else {
				tokenMap.put(token, new Integer[] { 1, 0 });
			}
		}

		// Check if the tokens in y are present in the map
		for (String token : y.getTokens()) {
			if (tokenMap.containsKey(token)) {
				Integer[] tokenCount = tokenMap.get(token);
				if (tokenCount[0] > tokenCount[1]) {
					overlap++;
					tokenCount[1]++;
					tokenMap.put(token, tokenCount);
				}
			}
		}

		return overlap;
	}

	private int overlap(Record r, Record y) {
		Record rSorted = sortRecord(r);
		Record ySorted = sortRecord(y);
		int overlap = 0;
		int i = 0, j = 0;
		boolean first = false;
		while (i < rSorted.getRecordSize() && j < ySorted.getRecordSize()) {
			if (rSorted.getToken(i).equalsIgnoreCase((ySorted.getToken(j)))) {
				overlap++;
				i++;
				j++;
			} else {
				if (rSorted.getToken(i).length() == ySorted.getToken(j)
						.length()) {
					if (first) {
						i++;
					} else {
						j++;
					}
					first = !first;
				} else if (rSorted.getToken(i).length() < ySorted.getToken(j)
						.length()) {
					i++;
					first = true;
				} else {
					j++;
					first = false;
				}
			}
		}
		return overlap;
	}

	private Record sortRecord(Record original) {
		Record sorted = new Record();
		int maxWordLength = 0;
		for (String token : original.getTokens()) {
			if (token.length() > maxWordLength) {
				maxWordLength = token.length();
			}
		}
		for (int i = 1; i <= maxWordLength; i++) {
			for (String token : original.getTokens()) {
				if (token.length() == i) {
					sorted.addToken(token);
				}
			}
		}
		return sorted;
	}

	private Map<String, List<Integer>> createInvInxList() {
		Map<String, List<Integer>> invertedIndeces = new HashMap<String, List<Integer>>();
		for (Record record : getDocuments()) {
			for (String token : record.getTokens()) {
				if (!invertedIndeces.containsKey(token)) {
					invertedIndeces.put(token, new ArrayList<Integer>());
				}
			}
		}
		return invertedIndeces;
	}

	private void setDocuments(Record[] documents) {
		this.documents = documents;
	}

	public Record[] getDocuments() {
		return documents;
	}
}
